package mianshi.leetcode.dp.medium;

public class 最长回文子串5 {
    public static void main(String[] args) {

    }
    /**
     * 中心扩散方法 ok
     * @param str
     * @return
     */
    public static String longestPalindrome(String str) {
        if (str == null || str.equals("")) {
            return "";
        }
        if (str.length() == 1) {
            return str;
        }
        if (str.length() == 2) {
            if (str.charAt(0) == str.charAt(1)) {
                return str;
            } else {
                return str.charAt(0)+"";
            }
        }
        int max = 1;
        int a = 0, b = 0;//a和b为最长回文子串的初始和结束索引位置
        for (int i = 0; i < str.length(); i++) {
            //中心点是单数
            int start = i;
            int end = i;
            //越界判断
            while (start >= 0 && end <= str.length() - 1) {
                //判断字符两端字符是否相等，不相等表示不是回文字符串
                if (str.charAt(start) == str.charAt(end)) {
                    if (end - start + 1 > max) {
                        a = start;
                        b = end;
                        max = Math.max(max, end - start + 1);
                    }
                    //前后指针移动一位
                    start--;
                    end++;
                } else {
                    break;
                }
            }
            //中心点是双数
            start = i;
            end = i + 1;
            //同理
            while (start >= 0 && end <= str.length() - 1) {
                if (str.charAt(start) == str.charAt(end)) {
                    if (end - start + 1 > max) {
                        a = start;
                        b = end;
                        max = Math.max(max, end - start + 1);
                    }
                    start--;
                    end++;
                } else {
                    break;
                }
            }

        }
        if (max == 1) {
            return str.charAt(0) + "";
        } else {
            return str.substring(a, b + 1);
        }

    }
}
